|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
|
|
Šachové úlohy v kombinatorice
Chybová, Lucie ; Slavík, Antonín (vedoucí práce) ; Šmíd, Dalibor (oponent)
Diplomová práce pojednává o matematických úlohách souvisejících se šacho- vými figurami. Řešení úloh jsou většinou elementární (někdy však velmi vynalé- zavá), v některých případech využívají základní poznatky z teorie grafů. Postupně se zaměřujeme na procházky figur po obdélníkových šachovnicích a dále na tzv. nezávislost a dominanci figur na čtvercových šachovnicích. Text je doplněn vel- kým množstvím obrázků s ukázkami konkrétních řešení daných úloh.
|
|
|
Aproximace nezávislosti rovinných grafů
Berg, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
Problém nezávislé množiny je dobře známý NP-úplný problém, který je NP-úplný i pro rovinné grafy. Ale na rozdíl od obecných grafů, pro rovinné grafy existuje polynomiální aproximační schéma. Popíšeme přesný algoritmus pro hledání největší nezávislé množiny v rovinných grafech založený na dynamickém programování. Tento přesný algoritmus lze jednoduše upravit na polynomiální aproximační schéma. Obě jeho verze jsme implemen- tovali a otestovali. Při tom jsme používali několik generátorů náhodných rovinných grafů. Přesný algoritmus jsme experimentálně srovnávali s dalšími dvěma algoritmy. Aproximační algoritmus jsme srovnávali s jeho přesnou verzí a měřili skutečný aproximační poměr a také jeho časovou náročnost v porovnání s přesnou verzí. Zjistili jsme, že přesný algoritmus na zvolených grafech většinou dokončí výpočet rychleji než ostatní dva algoritmy. Také jsme zjistili, že aproximační verze má vzhledem k teoretickému minimu většinou lepší apro- ximační poměr s dobrou časovou složitostí. 1
|
|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
host ::
RSS.